package com.example.demo.huawei;

/**
 * 最长回文字串
 */
public class Main21 {
    public static void main(String[] args) {
        System.out.println(new Main21().longestPalindrome("babad"));
    }
    // 记录最长回纹字串

    public String longestPalindrome(String s) {
        int length = s.length();
        int maxStart = 0;
        int maxLength = 0;
        for (int i = 0; i< length; i++) {
            // j=0表示中心节点只有 i，j=1，表示中心节点有两个 i，i+1;
            for (int j=0; j <=1; j++) {
                int l = i;
                int r = i+j;

                while(l >=0 && r < length && s.charAt(l) == s.charAt(r)){
                    l--;
                    r++;
                }

                // 回溯到回文字符串的起始和结束位置
                l++;
                r--;

                // 比较并保存最长的字符串起始位置和长度。
                if (maxLength < r - l + 1) {
                    maxLength = r - l + 1;
                    maxStart = l;
                }
            }
        }

        return s.substring(maxStart, maxStart + maxLength);
    }

}
